﻿// 0921train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
软盘中文件内容总大小最大
已知该软盘容量为1474560字节
文件占用的软盘空间都是按块分配的，每个块大小为512个字节
一个块只能被一个文件使用
拷贝到软盘中的文件必须是完整的，且不能采取任何压缩技术

输入描述
第1行为一个整数N，表示计算机中的文件数量。1 ≤ N ≤ 1000
接下来的第2行到第N+1行(共N行)，每行为一个整数，表示每个文件的大小Si，单位为字节
0 ≤ i < N,0 ≤ Si <= 1474560

输出描述
科学家最多能拷贝的文件总大小
备注
为了充分利用软盘空间，将每个文件在软盘上占用的块记录到本子上
即真正占用软盘空间的只有文件内容本身

输入
3
737270
737272
737288
输出
1474542
 */
class Solution01
{
public:
    Solution01(vector<int>&origin_v)
    {
        //软盘容量为1474560字节，每个块大小为512个字节
        double total = 1474560;
        double split = 512;
        int total_weight = total / split;

        int v_size = origin_v.size();
        //int total_val = accumulate(origin_v.begin(), origin_v.end(), 0);
        vector<int>weight_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            int curr_w = ceil(double(origin_v[i]) / split);
            weight_v[i] = curr_w;
        }

        vector<int>dynamic_v(total_weight + 1, INT_MIN);
        dynamic_v[0] = 0; //占据0空间，价值0

        for (int i=0; i<v_size; i++)
        {
            int curr_w = weight_v[i];
            for (int sum_w=total_weight; sum_w>=0; sum_w--)
            {
	            //转移方程 dp[sum_w]=dp[sum_w-curr_w]+origin_v[i]
                if (sum_w - curr_w < 0) continue;
                if (dynamic_v[sum_w - curr_w] == INT_MIN) continue;
                int curr_val = dynamic_v[sum_w - curr_w] + origin_v[i];
                dynamic_v[sum_w] = max(curr_val, dynamic_v[sum_w]);
            }
            //for---
        }

        int result = *max_element(dynamic_v.begin(), dynamic_v.end());
        cout << result;
        //Solution01
    }
};


/*
游戏规则如下：有 N 个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球
每个小桶装的小球数量记录在数组bucketBallNums中
游戏开始时，要求所有桶的小球总数不能超过SUM

如果小球总数超过SUM，
则需对所有的小桶统一设置一个尽可能大的容量最大值maxCapacity
并需将超过容量最大值的小球拿出来
直至所有小桶里的小球数量均不大于maxCapacity

请您根据输入的数据，计算出尽可能大的容量最大值maxCapacity，
并输出从每个小桶里拿出的小球数量

限制规则一
如果所有小桶的小球总和小于SUM，则无需设置容量值，并且无需从小桶中拿球出来，返回结果[]

限制规则二
如果所有小桶的小球总和大于SUM，则需设置一个尽可能大的容量最大值maxCapacity，
并且需从小桶中拿球出来，返回从每个小桶拿出的小球数量组成的数组

输入
第一行输入2个正整数，数字之间使用空格隔开
其中第一个数字表示SUM，第二个数字表示bucketBallNums数组长度；
第二行输入N个正整数，数字之间使用空格隔开，表示bucketBallNums的每一项

示例1
输入
14 7
2 3 2 5 5 1 4
输出
[0, 1, 0, 3, 3, 0, 2]

小球总数为22，SUM = 14，超出范围了，需从小桶取球。
- maxCapacity = 1，取出球后，1 1 1 1 1 1 1， 桶里剩余小球总和为7，远小于14
- maxCapacity = 2，取出球后，2 2 2 2 2 1 2，桶里剩余小球总和为13，小于14
- maxCapacity = 3，取出球后，2 3 2 3 3 1 3，桶里剩余小球总和为16，大于14
因此选择maxCapacity为2 ，每个小桶小球数量大于 2 的都需要拿出来

1 7
2 3 2 5 5 1 4
 */
class Solution02
{
public:
    bool checkVerify(long long num_limit, vector<long long>& num_vec)
    {
        long long curr_sum = 0;
        for (auto&curr:num_vec)
        {
            if (curr < num_limit)curr_sum += curr;
            else curr_sum += num_limit;
        }

        return curr_sum <= sum_limit;
	    //checkVerify
    }
    Solution02(long long limit, vector<long long>&num_vec)
    {
        //拿出球的范围1-max(num_vec)
        long long total_sum = accumulate(num_vec.begin(), num_vec.end(), 0LL);
        if (total_sum<=limit)
        {
            cout << "[]";
            return;
        }
        sum_limit = limit;

        long long max_num = *max_element(num_vec.begin(), num_vec.end());
        long long left = 0, right = max_num+1;
        long long max_num_limit = INT_MAX;
        while (left<right)
        {
            long long mid = left + (right - left) / 2;
            if (checkVerify(mid, num_vec))
            {
	            //增大容量限制
                max_num_limit = mid;
                left = mid + 1;
            }
            else
            {
                right = mid;
            }

        }

        int v_size = num_vec.size();
        vector<long long>result(v_size);
        for (int i=0; i<v_size; i++)
        {
            if (num_vec[i]>max_num_limit)
            {
                result[i] = num_vec[i] - max_num_limit;
            }
            else
            {
                result[i] = 0;
            }
        }

        cout << '[';
        for (int i=0; i<v_size; i++)
        {
            cout << result[i];
            if (i!=v_size-1)
            {
                cout << ','<<' ';
            }
        }
        cout << ']';
	    //Solution02
    }
private:
    long long sum_limit = 0;
};


/*
 现在给定可以种树的坑位的数量和位置，以及需要种多少棵树苗
 问树苗之间的最小间距是多少时，可以保证种的最均匀（两棵树苗之间的最小间距最大）
输入
输入三行：
- 第一行一个整数：坑位的数量
- 第二行以空格分隔的数组：坑位的位置
- 第三行一个整数：需要种植树苗的数量
输出
树苗之间的最小间距

输入
7
1 3 6 7 8 11 13
3
输出
6
三颗树苗分别种在 1、7、13 的位置，可以保证种的最均匀，树苗之间的最小间距为 6
如果选择最小间距为 7，则无法种下3颗树苗

 */
class Solution03
{
public:
    bool checkVerify(int curr_len, vector<int>&num_vec, int target)
    {
        int count = 1;
        int prev = num_vec[0];

        int v_size = num_vec.size();
        for (int i=1; i<v_size; i++)
        {
	        if (num_vec[i]-prev>=curr_len)
	        {
                count += 1;
                prev = num_vec[i];
	        }
        }

        return count >= target;
	    //checkVerify
    }

    Solution03(vector<int>&num_vec, int target)
    {
        if (target==1)
        {
            cout << 0;
            return;
        }

        sort(num_vec.begin(), num_vec.end());

        int max_num = *max_element(num_vec.begin(), num_vec.end());
        int left = 0, right = max_num;

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (checkVerify(mid,num_vec,target))
            {
                //满足要求，增大间隔
                result = mid;
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
            //while
        }

        cout << result;
	    //Solution03
    }
};


/*
某农场主管理了一大片果园，fields 表示不同果林的面积，单位：m^2
现在要为所有的果林施肥且必须在 n天之内完成，否则影响收成
小布是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业
假设施肥机的能效为 k，单位: m^2/day
请问至少租赁能效 k 为多少的施肥机才能确保不影响收成？
如果无法完成施肥任务，则返回 -1

输入描述
第一行输入为 m 和 n，m 表示 fields 中的元素个数
n 表示施肥任务必须在 n 天内 (含 n 天) 完成
第二行输入为 fields，fields[i]表示果林 i 的面积，单位: m^2

输出描述
对于每组数据，输出最小施肥机的能效 k，无多余空格

输入
5 7
5 7 9 15 10
输出
9
当能效 k 为 9 时，
fields[0]需要 1 天，fields[1]需要 1 天，fields[2]需要 1 天，fields[3]需要 2 天，
fields[4]需要 2 天，共需要 7 天，不会影响收成
 */
class Solution04
{
public:
    bool checkVerify(int speed, int limit, vector<int>& num_vec)
    {
        int count = 0;
        for (auto&num:num_vec)
        {
            int curr = ceil(double(num) / double(speed));
            count += curr;
        }

        return count <= limit;

        //checkVerify
    }

    Solution04(int limit, vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        if (limit<v_size)
        {
            cout << -1;
            return;
        }
        int max_num = *max_element(num_vec.begin(), num_vec.end());
        int left = 1, right = max_num + 1;

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (checkVerify(mid, limit, num_vec))
            {
                //满足要求，减少速度
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
            //while
        }

        cout << result;
	    //Solution04
    }
};


/*
给定一个数组X和正整数K，请找出使表达式：
X[i] - X[i+1] - ... - X[i+K-1]
结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i
其中，数组中位数：长度为N的数组，按照元素的值大小升序排列后，下标为N/2元素的值

输入
[50,50,2,3],2
输出
1

中位数为50: [50,50,2,3]升序排序后变成[2,3,50,50]，中位数为下标4/2=2的元素50;
计算结果为1: X[50,50,2,3]根据题目计算X[i] - … - X[i+K-1]得出三个数
0 (X[0]-X[1]= 50-50)
48 (X[1]-X[2] = 50-2)
-1 (X[2]-X[3]= 2-3)
其中48最接近50，因此返回下标1
 */
class Solution05
{
public:
    int getPos(vector<int>&nums, int K)
    {
        vector<int>sort_vec = nums;
        sort(sort_vec.begin(), sort_vec.end());

        int v_size = nums.size();
        int middle_num = sort_vec[v_size / 2];

        vector<int>pre_sum(v_size + 1);
        for (int i = 1; i <= v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1];
        }

        int result_i = -1;
        int min_diff = INT_MAX;

        for (int i = 0; i + K <= v_size; i++)
        {
            if (i == v_size) break;
            int sum = pre_sum[i + K] - pre_sum[i + 1];
            int curr_num = nums[i] - sum;
            int curr_diff = abs(middle_num - curr_num);

            if (curr_diff <= min_diff)
            {
                result_i = i;
                min_diff = curr_diff;
            }
        }

        return result_i;
    }

    Solution05(vector<int>&nums, int K)
    {
        
        //X[i] - X[i+1] - ... - X[i+K-1]
        //X[i]-(pre_sum[i+K]-pre_sum[i])
        cout << getPos(nums, K);
	    //Solution05
    }
};


/*
服务之间交换的接口成功率作为服务调用关键质量特性
某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值
数组中的数值为 0~100 的整数，给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值
即平均失败率小于等于 minAverageLost，找出数组中最长时间段，如果未找到则直接返回 NULL

输入描述
输入有两行内容
第一行为minAverageLost
第二行为数组，数组元素通过空格" "分隔，minAverageLost 及数组中元素取值范围为 0~100 的整数，
数组元素的个数不会超过 100 个

输出描述
找出平均值小于等于 minAverageLost 的最长时间段
输出数组下标对，格式{beginIndex}-{endIndx}(下标从 0 开始)
如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格" "拼
多个下标对按下标从小到大排序

输入
1
0 1 2 3 4
输出
0-2
输入解释：minAverageLost=1，数组[0, 1, 2, 3, 4]
前 3 个元素的平均值为 1，因此数组第一个至第三个数组下标，即 0-2
 */
class Solution06
{
public:
    Solution06 (int limit, vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        vector<int>pre_sum(v_size + 1);
        for (int i=1; i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + num_vec[i - 1];
        }


        int max_length = 0;
        vector<vector<int>>result;

        for (int i=1; i<=v_size;i++)
        {
            for (int prev=0; prev<i; prev++)
            {
                double curr_sum = pre_sum[i] - pre_sum[prev];
                double length = i - prev;
                double average = curr_sum / length;

                if (average > limit) continue;

                if (length > max_length)
                {
                    result.clear();
                    result.push_back({ prev,i-1 });
                    max_length = length;
                }
                else if (length == max_length)
                {
                    result.push_back({ prev, i-1 });
                }
            }
        }

        if (result.empty())
        {
            cout << NULL;
            return;
        }

        int result_size = result.size();
        sort(result.begin(), result.end(), [](vector<int>& vec_1, vector<int>& vec_2)
            {
                return vec_1[0] < vec_2[0];
            });

        for (int i=0; i<result_size; i++)
        {
            cout << result[i][0] << '-' << result[i][1];
            if (i!=result_size-1)
            {
                cout << ' ';
            }
        }

	    //Solution06
    }
};


int main()
{
	{
        int limit; cin >> limit;
        cin.ignore();
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }
        Solution06 solu(limit, num_vec);

        return 0;
	}
	{
        vector<int>nums = { 50,50,2,3 };
        int K = 2;
        Solution05 solu(nums, K);

        return 0;
	}
	{
        int v_size, limit;
        cin >> v_size >> limit;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution04 solu(limit, num_vec);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        int target;
        cin >> target;

        Solution03 solu(num_vec, target);

        return 0;
	}
	{
        long long sum_limit, v_size;
        cin >> sum_limit >> v_size;
        vector<long long>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution02 solu(sum_limit, num_vec);

        return 0;
	}
    int v_size;
    cin >> v_size;
    vector<int>origin_v(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> origin_v[i];
    }
    Solution01 solu(origin_v);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
